package com.dubious.interview.euler.pandigital;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import com.dubious.interview.euler.Utilities;

/**
 * Class that allows one to iterate over all pandigital numbers with digits in a range.
 * The iteration is performed from a ceiling downward.
 */
public class PandigitalNumbers implements Iterable<Long>, Iterator<Long>
{        
    /*
     * Is there a pattern in counting down the pandigital numbers?
     * Consider 1 to 9 pandigital numbers.
     * 987654321
     * 987654312
     * 987654231
     * 987654213
     * 987654132
     * 987654123
     * 987653421
     * ...
     * 
     * 849123756 becomes
     * 849123675
     * - start from the last digit and continue left as long as the digits decrease
     * - on the first increase, reduce this digit to the next highest in the available set.
     * 
     * We can generate these with a recursive algorithm, also, but it is not conducive to one-by-one iteration
     */

    private List<Integer> setDigits;
    private List<Integer> remainingDigits;
    private Long lastValue = Long.MAX_VALUE;

    public PandigitalNumbers(int lowDigit, int highDigit, long ceiling)
    {
        // initialize the "set" digits and verify they meet requirements for a ceiling
        setDigits = Utilities.extractDigits(ceiling);
        if(setDigits.size() != highDigit - lowDigit + 1)
        {
            throw new RuntimeException("Ceiling does not have 9 digits");
        }
        for(int i = lowDigit; i <= highDigit; i++)
        {
            if(!setDigits.contains(Integer.valueOf(i)))
            {
                throw new RuntimeException("Ceiling does not contain digit " + i);
            }
        }
        
        // initialize the remaining digits to be empty
        remainingDigits = new LinkedList<Integer>();
    }
    
    @Override
    public boolean hasNext() {
        // note that we don't consider the very-last pandigital number as part of this iterator
        return lastValue > 123456789;
    }

    @Override
    public Long next() {
        if(setDigits.size() > 0)
        {
            // put numbers back into remainingDigits bucket, starting from end of setDigits as long
            // as digits are in decreasing value
            do
            {
                // this add preserves highest to lowest value in the remainingDigits
                remainingDigits.add(setDigits.remove(setDigits.size() - 1));
            } while(setDigits.get(setDigits.size() - 1) < remainingDigits.get(remainingDigits.size() - 1));
            
            // have reached a digit in setDigits that was not less than the digit after it
            // replace it with the highest remaining digit with lower value
            Integer swapDigit = setDigits.remove(setDigits.size() - 1);
            for(int i = 0; i < remainingDigits.size(); i++)
            {
                if(remainingDigits.get(i) < swapDigit)
                {
                    setDigits.add(remainingDigits.get(i));
                    remainingDigits.set(i, swapDigit);
                    break;
                }
            }
        }
        
        // append the digits that remain into the setDigits
        while(remainingDigits.size() > 0)
        {
            setDigits.add(remainingDigits.remove(0));
        }
        
        // generate the Integer from the digits
        lastValue = 0L;
        for(int i = 0; i < setDigits.size(); i++)
        {
            lastValue += setDigits.get(setDigits.size() - 1 - i) * (long)Math.pow(10, i);
        }
        
        return lastValue;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not Supported");
    }

    @Override
    public Iterator<Long> iterator() {
        return this;
    }        
}
